package lc20240615;

/**
  * @description 单词搜索
  * @author 不知名帅哥
  * @date 2024/6/15 17:52
  * @version 1.0
*/
public class WordSearch {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == words[0] && dfs(board, words, m, n, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board,char[] words,int m,int n,int x,int y,int index,boolean[][] visited){
        //如果递归到单词的末尾，即为找到正确的路径，返回true。
        if (index== words.length){
            return true;
        }
        //终止条件，剪枝
        if (x<0||y<0||x>= m||y>=n||visited[x][y]||board[x][y]!=words[index]){
            return false;
        }
        //标记当前节点为访问过的节点
        visited[x][y]=true;
        //判断上下左右所有的情况。
        boolean found=dfs(board,words,m,n,x+1,y,index+1,visited)||
                dfs(board, words, m, n, x, y+1, index+1, visited)||
                dfs(board, words, m, n, x-1, y, index+1, visited)||
                dfs(board,words,m,n,x,y-1,index+1,visited);
        //回溯，恢复状态
        visited[x][y]=false;
        return found;
    }

    public static void main(String[] args) {
        char[][] board={
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','F'}
        };
        String words="ABCCED";
        WordSearch wordSearch=new WordSearch();
        System.out.println(wordSearch.exist(board, words));
    }
}
